package LearnAlgorithm.d_标准查找算法and标准排序算法;

public class a2二分查找 {

	public static void main(String[] args) {
		int[] arr = new int[] {1,2,3,4,5,6,7,8,9};
		int search1 = search1(arr, 0, arr.length-1, 9);
		System.out.println("target index: " + search1);
	}

	/**
	 * 二分查找
	 * 需要有顺序的数组
	 * 当前只能查找不重复元素的有序数组
	 * O(logN)
	 * @param arr
	 * @param low
	 * @param height
	 * @param key
	 * @return
	 */
	private static int search1(int[] arr, int low, int height, int key) {
		if (low > height) {
			return -1;
		}
		int mid = low + ((height - low) >>> 1);//向下取整。如22.5 ---> 22
		int midValue = arr[mid];
		if (midValue < key) {
			return search1(arr, mid+1, height, key);
		} else if (midValue > key) {
			return search1(arr, low, mid-1, key);
		} else if (midValue == key) {
			return mid;
		} else {
			return -1;
		}
	}
}
